public class Solution3 {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return ;
        }

        // 1. 找出链表的中间节点 - 快慢双指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 把后半部分（slow.next后部分）逆序 - 头插法
        ListNode head2 = new ListNode();
        ListNode cur = slow.next;
        slow.next = null; // 把两个链表分离
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        // 3. 合并两个链表 - 双指针
        ListNode cur1 = head;
        ListNode cur2 = head2.next;
        ListNode ret = new ListNode();
        ListNode prev = ret;
        while(cur1 != null) {
            // 先放第一个链表
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            // 再合并第二个链表
            if(cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
